package com.sheng.leetcode.year2022.month09.day30;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/30
 *<p>
 * 面试题 01.08. 零矩阵<p>
 *<p>
 * 编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。<p>
 *<p>
 * 示例 1：<p>
 * 输入：<p>
 * [<p>
 *   [1,1,1],<p>
 *   [1,0,1],<p>
 *   [1,1,1]<p>
 * ]<p>
 * 输出：<p>
 * [<p>
 *   [1,0,1],<p>
 *   [0,0,0],<p>
 *   [1,0,1]<p>
 * ]<p>
 *<p>
 * 示例 2：<p>
 * 输入：<p>
 * [<p>
 *   [0,1,2,0],<p>
 *   [3,4,5,2],<p>
 *   [1,3,1,5]<p>
 * ]<p>
 * 输出：<p>
 * [<p>
 *   [0,0,0,0],<p>
 *   [0,4,5,0],<p>
 *   [0,3,1,0]<p>
 * ]<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/zero-matrix-lcci">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCodeSetZeroes {

    @Test
    public void test01() {
        int[][] matrix = {
                {1,1,1},
                {1,0,1},
                {1,1,1}
        };
//        int[][] matrix = {
//                {0,1,2,0},
//                {3,4,5,2},
//                {1,3,1,5}
//        };
        new Solution().setZeroes(matrix);
    }
}
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 存放横/竖坐标上等于0的元素的坐标
        List<Integer> mList = new ArrayList<>();
        List<Integer> nList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 元素为0时将对应的坐标添加到集合中
                if (matrix[i][j] == 0) {
                    mList.add(i);
                    nList.add(j);
                }
            }
        }
        // 循环集合，将对应的一行/列全部置为0
        for (Integer integer : mList) {
            for (int i = 0; i < n; i++) {
                matrix[integer][i] = 0;
            }
        }
        for (Integer integer : nList) {
            for (int i = 0; i < m; i++) {
                matrix[i][integer] = 0;
            }
        }
    }
}
